<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>Document</title>
  </head>
  <body>
    <script>
      // 菲波那切数列
      // 递归的时间复杂度,子问题个数乘以一个字问题解决时间
      function fb(n) {
        if (n == 1 || n == 2) {
          return 1;
        }
        return fb(n - 1) + fb(n - 2);
      }

      // 优化,有些子问题 重复计算,,采用 备忘录
      function fb1(n) {
        var memo = {};
        return helper(n, memo);
      }
      function helper(n, memo) {
        if (n == 1 || n == 2) {
          return 1;
        }
        if (memo[n]) {
          return memo[n];
        } else {
          memo[n] = helper(n - 1, memo) + helper(n - 2, memo);
          return memo[n];
        }
      }

      // 动态规划 状态转移方程 dp[i] = dp[i-1]+dp[i+1]

      function fb2(n) {
        var dp = [];
        dp[0] = 0;
        dp[1] = dp[2] = 1;
        for (var i = 3; i <= n; i++) {
          dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
      }
      function fb3(n) {
        if (n == 1 || n == 2) {
          return 1;
        }
        // 只关注前两个
        var cur = 1;
        var prev = 1;
        for (var i = 3; i <= n; i++) {
          var sum = cur + prev;
          prev = cur;
          cur = sum;
        }
        return sum;
      }
      console.log(fb(6), fb1(6), fb2(6), fb3(6));

      // 凑零钱问题
      // 给你k种面值的硬币，面值分别为c1, c2 ... ck，每种硬币的数量无限，再给一个总金额amount，
      // 问你最少需要几枚硬币凑出这个金额，如果不可能凑出，算法返回 -1
      // 比如说k = 3，面值分别为 1，2，5，总金额amount = 11。那么最少需要 3 枚硬币凑出，即 11 = 5 + 5 + 1

      // 就是把所有可能的凑硬币方法都穷举出来，然后找找看最少需要多少枚硬币。

      function coinChange(coins, amount) {
        // coins 零钱数组
        var memo = {};
        function dp(n) {
          if (n in memo) {
            // console.log("哈哈哈");
            return memo[n];
          }
          if (n == 0) {
            return 0;
          }
          if (n < 0) {
            return -1;
          }
          var res = Infinity;
          for (var i = 0; i < coins.length; i++) {
            var tmp = dp(n - coins[i]);
            if (tmp == -1) {
              continue;
            }
            res = Math.min(res, 1 + tmp);
          }
          // 记入备忘录
          if (res != Infinity) {
            memo[n] = res;
          } else {
            return -1;
          }
          return memo[n];
        }
        return dp(amount);
      }

      console.log(coinChange([1, 2, 5], 11));

      // dp数组 迭代
      // dp[i] = x表示，当目标金额为i时，至少需要x枚硬币。
      function changeCoin(coins, amount) {
        var dp = new Array(amount + 1).fill(amount + 1);
        console.log(dp);
        dp[0] = 0;
        for (var i = 0; i < dp.length; i++) {
          for (var j = 0; j < coins.length; j++) {
            if (i - coins[j] < 0) {
              continue;
            }

            dp[i] = Math.min(dp[i], 1 + dp[i - coins[j]]);
          }
        }
        return dp[amount] == amount + 1 ? -1 : dp[amount];
      }
      console.log(changeCoin([1, 2, 5], 11));
    </script>
  </body>
</html>
